#include <vector>

using namespace std;


//成绩统计
// #include <iostream>
// using namespace std;
// int main()
// {
//   int number = 0;
//   int pass = 0;
//   int great = 0;
//   int score = 0;

//   cin >> number;
//   for (int i = 0; i<number; ++i)
//   {
//     cin >> score;
//     if (score >= 60)
//     {
//       ++pass;
//     }
//     if (score >= 85)
//     {
//       ++great;
//     }
//   }

//   cout << ( (int)(((pass/ (number*1.0) )*100.0)+0.5) ) << "%" << endl;
//   cout << ( (int)(((great/ (number*1.0) )*100.0)+0.5) ) << "%" << endl;

//   return 0;
// }

class Solution {
public:

    //剑指 Offer 57. 和为s的两个数字
    //法一
    // bool binary_serch(vector<int>& nums,int start, int target)
    // {
    //     int left = start;
    //     int right = nums.size() - 1;
    //     while (left <= right)
    //     {
    //         int mid = (left + right) >> 1;
    //         if (nums[mid] == target)
    //         {
    //             return true;
    //         }
    //         else if (nums[mid] < target)
    //         {
    //             left = mid + 1;
    //         }
    //         else 
    //         {
    //             right = mid - 1;
    //         }
    //     }
    //     return false;
    // }

    // vector<int> twoSum(vector<int>& nums, int target) {
    //     for (int i = 0; i<nums.size(); ++i)
    //     {
    //         int other = target - nums[i];
    //         if (binary_serch(nums, i, other))
    //         {
    //             return { nums[i], other };
    //         }
    //     }

    //     return {};
    // }

    //法二
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right)
        {
            int sum = nums[left] + nums[right];
            if (sum == target)
            {
                return { nums[left],nums[right] };
            }
            else if (sum > target)
            {
                --right;
            }
            else 
            {
                ++left;
            }
        }
        return {};
    }
};